Zermelo–Fraenkel set theory

In mathematics, Zermelo–Fraenkel set theory with the axiom of choice, named after mathematicians Ernst Zermelo and Abraham Fraenkel and commonly abbreviated ZFC, is one of several axiomatic systems that were proposed in the early twentieth century to formulate a theory of sets without the paradoxes of naive set theory such as Russell's paradox. Specifically, ZFC does not allow unrestricted comprehension. Today ZFC is the standard form of axiomatic set theory and as such is the most common foundation of mathematics.

ZFC has a single primitive ontological notion, that of a hereditary well-founded set, and a single ontological assumption, namely that all individuals in the universe of discourse are such sets. Thus, ZFC is a set theory without urelements (elements of sets which are not themselves sets). ZFC does not formalize the notion of classes (collections of mathematical objects defined by a property shared by their members) and specifically does not include proper classes (objects that have members but cannot be members themselves).

ZFC is a one-sorted theory in first-order logic. The signature has equality and a single primitive binary relation, set membership, which is usually denoted ∈. The formula a ∈ b means that the set a is a member of the set b (which is also read, "a is an element of b" or "a is in b").

There are many equivalent formulations of the ZFC axioms. Most of the ZFC axioms state the existence of particular sets. For example, the axiom of pairing says that given any two sets a and b there is a new set {a, b} containing exactly a and b. Other axioms describe properties of set membership. A goal of the ZFC axioms is that each axiom should be true if interpreted as a statement about the collection of all sets in the von Neumann universe (also known as the cumulative hierarchy).

The metamathematics of ZFC has been extensively studied. Landmark results in this area established the independence of the continuum hypothesis from ZFC, and of the axiom of choice from the remaining ZFC axioms.

Contents

History

In 1908, Ernst Zermelo proposed the first axiomatic set theory, Zermelo set theory. This axiomatic theory did not allow the construction of the ordinal numbers. While most of "ordinary mathematics" can be developed without ever using ordinals, ordinals are an essential tool in most set-theoretic investigations. Moreover, one of Zermelo's axioms invoked a concept, that of a "definite" property, whose operational meaning was not clear. In 1922, Abraham Fraenkel and Thoralf Skolem independently proposed operationalizing a "definite" property as one that could be formulated as a first order theory whose atomic formulas were limited to set membership and identity. They also independently proposed replacing the axiom schema of specification with the axiom schema of replacement. Appending this schema, as well as the axiom of regularity (first proposed by Dimitry Mirimanoff in 1917), to Zermelo set theory yields the theory denoted by ZF. Adding to ZF either the axiom of choice (AC) or a statement that is equivalent to it yields ZFC.

The axioms

There are many equivalent formulations of the ZFC axioms; for a rich but somewhat dated discussion of this fact, see Fraenkel et al. (1973). The following particular axiom set is from Kunen (1980). The axioms per se are expressed in the symbolism of first order logic. The associated English prose is only intended to aid the intuition.

All formulations of ZFC imply that at least one set exists. Kunen includes an axiom that directly asserts the existence of a set, in addition to the axioms given below. Its omission here can be justified in two ways. Many authors require a nonempty domain of discourse as part of the semantics of the first-order logic in which ZFC is formalized. Also the axiom of infinity (below) also implies that at least one set exists, as it begins with an existential quantifier, so its presence makes superfluous an axiom (merely) asserting the existence of a set.

1. Axiom of extensionality

Main article: Axiom of extensionality

Two sets are equal (are the same set) if they have the same elements.

\forall x \forall y [ \forall z (z \in x \Leftrightarrow z \in y) \Rightarrow x = y].

The converse of this axiom follows from the substitution property of equality. If the background logic does not include equality "=", x=y may be defined as an abbreviation for the following formula (Hatcher 1982, p. 138, def. 1):

\forall z [ z \in x \Leftrightarrow z \in y] \land \forall z [x \in z \Leftrightarrow y \in z].

In this case, the axiom of extensionality can be reformulated as

\forall x \forall y [ \forall z (z \in x \Leftrightarrow z \in y) \Rightarrow \forall z (x \in z \Leftrightarrow y \in z) ],

which says that if x and y have the same elements, then they belong to the same sets (Fraenkel et al. 1973).

2. Axiom of regularity (also called the Axiom of foundation)

Main article: Axiom of regularity

Every non-empty set x contains a member y such that x and y are disjoint sets.

\forall x [ \exists a ( a \in x) \Rightarrow \exists y ( y \in x \land \lnot \exists z (z \in y \land z \in x))].

3. Axiom schema of specification (also called the axiom schema of separation or of restricted comprehension)

Main article: Axiom schema of specification

If z is a set, and \phi\! is any property which may characterize the elements x of z, then there is a subset y of z containing those x in z which satisfy the property. The "restriction" to z is necessary to avoid Russell's paradox and its variants. More formally, let \phi\! be any formula in the language of ZFC with free variables among x,z,w_1,\ldots,w_n\!. So y is not free in \phi\!. Then:

\forall z \forall w_1 \ldots w_n \exists y \forall x [x \in y \Leftrightarrow ( x \in z \land \phi )].

This axiom is part of Z, but can be redundant in ZF, in that it may follow from the axiom schema of replacement, with (as here) or without the axiom of the empty set.

The axiom of specification can be used to prove the existence of the empty set, denoted \varnothing, once the existence of at least one set is established (see above). A common way to do this is to use an instance of specification for a property which all sets do not have. For example, if w is a set which already exists, the empty set can be constructed as

\varnothing = \{u \in w \mid (u \in u) \land \lnot (u \in u) \}.

If the background logic includes equality, it is also possible to define the empty set as

\varnothing = \{u \in w \mid \lnot (u = u) \}.

Thus the axiom of the empty set is implied by the nine axioms presented here. The axiom of extensionality implies the empty set is unique, if it exists. It is common to make a definitional extension that adds the symbol \varnothing to the language of ZFC.

4. Axiom of pairing

Main article: Axiom of pairing

If x and y are sets, then there exists a set which contains x and y as elements.

\forall x \forall y \exist z (x \in z \land y \in z).

This axiom is part of Z, but is redundant in ZF because it follows from the axiom schema of replacement applied to any two-member set. The existence of such a set is assured by either the axiom of infinity, or by the axiom of the power set applied twice to the empty set.

5. Axiom of union

Main article: Axiom of union

For any set \mathcal{F} there is a set A containing every set that is a member of some member of \mathcal{F}.

\forall \mathcal{F} \,\exists A \, \forall Y\, \forall x [(x \in Y \land Y \in \mathcal{F}) \Rightarrow x \in A].

6. Axiom schema of replacement

Main article: Axiom schema of replacement

Let \phi \! be any formula in the language of ZFC whose free variables are among x,y,A,w_1,\ldots,w_n \!, so that in particular B is not free in \phi \!. Then:

\forall A\forall w_1,\ldots,w_n \bigl[ \forall x ( x\in A \Rightarrow \exists!y\,\phi ) \Rightarrow \exists B \forall x \bigl(x\in A \Rightarrow \exists y (y\in B \land \phi)\bigr)\bigr].

Less formally, this axiom states that if the domain of a definable function f is a set, and f(x) is a set for any x in that domain, then the range of f is a subclass of a set, subject to a restriction needed to avoid paradoxes. The form stated here, in which B may be larger than strictly necessary, is sometimes called the axiom schema of collection.

7. Axiom of infinity

Main article: Axiom of infinity

Let S(x)\! abbreviate x \cup \{x\} \!, where x \! is some set. Then there exists a set X such that the empty set \varnothing is a member of X and, whenever a set y is a member of X, then S(y)\! is also a member of X.

\exist X \left [\varnothing \in X \and \forall y (y \in X \Rightarrow S(y) \in X)\right ].

More colloquially, there exists a set X having infinitely many members. The minimal set X satisfying the axiom of infinity is the von Neumann ordinal ω, which can also be thought of as the set of natural numbers \mathbb{N}.

8. Axiom of power set

Main article: Axiom of power set

Let z \subseteq x abbreviate \forall q (q \in z \Rightarrow q \in x). For any set x, there is a set y which is a superset of the power set of x. The power set of x is the class whose members are all of the subsets of x.

\forall x \exists y \forall z [z \subseteq x \Rightarrow z \in y].

Alternative forms of axioms 1–8 are often encountered, some of which are listed in Jech (2003). Some ZF axiomatizations include an axiom asserting that the empty set exists. The axioms of pairing, union, replacement, and power set are often stated so that the members of the set x whose existence is being asserted are just those sets which the axiom asserts x must contain.

9. Well-ordering theorem

Main article: Well-ordering theorem

For any set X, there is a binary relation R which well-orders X. This means R is a linear order on X such that every nonempty subset of X has a member which is minimal under R.

\forall X \exists R ( R \;\mbox{well-orders}\; X).

Given axioms 1-8, there are many statements provably equivalent to axiom 9, the best known of which is the axiom of choice (AC), which goes as follows. Let X be a set whose members are all non-empty. Then there exists a function f from X to the union of the members of X, called a "choice function", such that for all Y ∈ X one has f(Y) ∈ Y. Since the existence of a choice function when X is a finite set is easily proved from axioms 1-8, AC only matters for certain infinite sets. AC is characterized as nonconstructive because it asserts the existence of a choice set but says nothing about how the choice set is to be "constructed." Much research has sought to characterize the definability (or lack thereof) of certain sets whose existence AC asserts.

Motivation via the cumulative hierarchy

One motivation for the ZFC axioms is the cumulative hierarchy of sets introduced by John von Neumann (Shoenfield 1977, sec. 2). In this viewpoint, the universe of set theory is built up in stages, with one stage for each ordinal number. At stage 0 there are no sets yet. At each following stage, a set is added to the universe if all of its elements have been added at previous stages. Thus the empty set is added at stage 1, and the set containing the empty set is added at stage 2; see Hinman (2005, p. 467). The collection of all sets that are obtained in this way, over all the stages, is known as V. The sets in V can be arranged into a hierarchy by assigning to each set the first stage at which that set was added to V.

It is provable that a set is in V if and only if the set is pure and well-founded; and provable that V satisfies all the axioms of ZFC, if the class of ordinals has appropriate reflection properties. For example, suppose that a set x is added at stage α, which means that every element of x was added at a stage earlier than α. Then every subset of x is also added at stage α, because all elements of any subset of x were also added before stage α. This means that any subset of x which the axiom of separation can construct is added at stage α, and that the powerset of x will be added at the next stage after α. For a complete argument that V satisfies ZFC see Shoenfield (1977).

The picture of the universe of sets stratified into the cumulative hierarchy is characteristic of ZFC and related axiomatic set theories such as Von Neumann–Bernays–Gödel set theory (often called NBG) and Morse–Kelley set theory. The cumulative hierarchy is not compatible with other set theories such as New Foundations.

It is possible to change the definition of V so that at each stage, instead of adding all the subsets of the union of the previous stages, subsets are only added if they are definable in a certain sense. This results in a more "narrow" hierarchy which gives the constructible universe L, which also satisfies all the axioms of ZFC, including the axiom of choice. It is independent from the ZFC axioms whether V = L. Although the structure of L is more regular and well behaved than that of V, few mathematicians argue that V = L should be added to ZFC as an additional axiom.

Metamathematics

The axiom schemata of replacement and separation each contain infinitely many instances. Montague (1961) included a result first proved in his 1957 Ph.D. thesis: if ZFC is consistent, it is impossible to axiomatize ZFC using only finitely many axioms. On the other hand, Von Neumann–Bernays–Gödel set theory (NBG) can be finitely axiomatized. The ontology of NBG includes proper classes as well as sets; a set is any class that can be a member of another class. NBG and ZFC are equivalent set theories in the sense that any theorem not mentioning classes and provable in one theory can be proved in the other.

Gödel's second incompleteness theorem says that a recursively axiomatizable system that can interpret Robinson arithmetic can prove its own consistency only if it is inconsistent. Moreover, Robinson arithmetic can be interpreted in general set theory, a small fragment of ZFC. Hence the consistency of ZFC cannot be proved within ZFC itself (unless it is actually inconsistent). Thus, to the extent that ZFC is identified with ordinary mathematics, the consistency of ZFC cannot be demonstrated in ordinary mathematics. The consistency of ZFC does follow from the existence of a weakly inaccessible cardinal, which is unprovable in ZFC if ZFC is consistent. Nevertheless, it is deemed unlikely that ZFC harbors an unsuspected contradiction; it is widely believed that if ZFC were inconsistent, that fact would have been uncovered by now. This much is certain — ZFC is immune to the classic paradoxes of naive set theory: Russell's paradox, the Burali-Forti paradox, and Cantor's paradox.

Abian and LaMacchia (1978) studied a subtheory of ZFC consisting of the axioms of extensionality, union, powerset, replacement, and choice. Using models, they proved this subtheory consistent, and proved that each of the axioms of extensionality, replacement, and power set is independent of the four remaining axioms of this subtheory. If this subtheory is augmented with the axiom of infinity, each of the axioms of union, choice, and infinity is independent of the five remaining axioms. Because non-well-founded set theory is a model of ZFC without the axiom of regularity, that axiom is independent of the other ZFC axioms.

If consistent, ZFC cannot prove the existence of the inaccessible cardinals that category theory requires. Huge sets of this nature are possible if ZF is augmented with Tarski's axiom (Tarski 1939). Assuming that axiom turns the axioms of infinity, power set, and choice (7 − 9 above) into theorems.

Independence in ZFC

Many important statements are independent of ZFC (see list of statements undecidable in ZFC). The independence is usually proved by forcing, whereby it is shown that every countable transitive model of ZFC (sometimes augmented with large cardinal axioms) can be expanded to satisfy the statement in question. A different expansion is then shown to satisfy the negation of the statement. An independence proof by forcing automatically proves independence from arithmetical statements, other concrete statements, and large cardinal axioms. Some statements independent of ZFC can be proven to hold in particular inner models, such as in the constructible universe. However, some statements that are true about constructible sets are not consistent with hypothesized large cardinal axioms.

Forcing proves that the following statements are independent of ZFC:

Remarks:

A variation on the method of forcing can also be used to demonstrate the consistency and unprovability of the axiom of choice, i.e., that the axiom of choice is independent of ZF. The consistency of choice can be (relatively) easily verified by proving that the inner model L satisfies choice. (Thus every model of ZF contains a submodel of ZFC, so that Con(ZF) implies Con(ZFC).) Since forcing preserves choice, we cannot directly produce a model contradicting choice from a model satisfying choice. However, we can use forcing to create a model which contains a suitable submodel, namely one satisfying ZF but not C.

Another method of proving independence results, one owing nothing to forcing, is based on Gödel's second incompleteness theorem. This approach employs the statement whose independence is being examined, to prove the existence of a set model of ZFC, in which case Con(ZFC) is true. Since ZFC satisfies the conditions of Gödel's second theorem, the consistency of ZFC is unprovable in ZFC (provided that ZFC is, in fact, consistent). Hence no statement allowing such a proof can be proved in ZFC. This method can prove that the existence of large cardinals is not provable in ZFC, but cannot prove that assuming such cardinals, given ZFC, is free of contradiction.

Criticisms

For criticism of set theory in general, see Objections to set theory

ZFC has been criticized both for being excessively strong and for being excessively weak, as well as for its failure to capture objects such as proper classes and the universal set.

Many mathematical theorems can be proven in much weaker systems than ZFC, such as Peano arithmetic and second order arithmetic (as explored by the program of reverse mathematics). Saunders Mac Lane and Solomon Feferman have both made this point. Some of "mainstream mathematics" (mathematics not directly connected with axiomatic set theory) is beyond Peano arithmetic and second order arithmetic, but still, all such mathematics can be carried out in ZC (Zermelo set theory with choice), another theory weaker than ZFC. Much of the power of ZFC, including the axiom of regularity and the axiom schema of replacement, is included primarily to facilitate the study of the set theory itself.

On the other hand, among axiomatic set theories, ZFC is comparatively weak. Unlike New Foundations, ZFC does not admit the existence of a universal set. Hence the universe of sets under ZFC is not closed under the elementary operations of the algebra of sets. Unlike von Neumann–Bernays–Gödel set theory and Morse–Kelley set theory (MK), ZFC does not admit the existence of proper classes. These ontological restrictions are required for ZFC to avoid Russell's paradox, but critics argue these restrictions make the ZFC axioms fail to capture the informal concept of set. A further comparative weakness of ZFC is that the axiom of choice included in ZFC is weaker than the axiom of global choice included in MK.

There are numerous mathematical statements undecidable in ZFC. These include the continuum hypothesis, the Whitehead problem, and the Normal Moore space conjecture. Some of these conjectures are provable with the addition of axioms such as Martin's axiom, large cardinal axioms to ZFC. Some others are decided in ZF+AD where AD is the axiom of determinacy, a strong supposition incompatible with choice. One attraction of large cardinal axioms is that they enable many results from ZF+AD to be established in ZFC adjoined by some large cardinal axiom (see projective determinacy). The Mizar system has adopted Tarski–Grothendieck set theory instead of ZFC so that proofs involving Grothendieck universes (encountered in category theory and algebraic geometry) can be formalized.

See also

Related axiomatic set theories:

References

External links